#include <iostream>
#include <vector>
#include <string>
#include <cmath>
#include <cstdlib>
#include <stdlib.h>
#include <cstdio>
#include <cstdint>
#include <ctime>
#include <stack>
#include <string>
#include <queue>
#include <unistd.h>
#include <limits.h>
#include <algorithm>

using namespace std;

class Solution {
public:
    vector<vector<vector<int>>> test;
    void vectorPush(vector<vector<int>> &des, vector<int> src){
        if (!des.empty()){
            if (des.back()[0] == src[0]){
                if (src[1] > des.back()[1]){
                    des.back()[1] = src[1];
                }
            }else{
                des.push_back(src);
            }
        }else{
            des.push_back(src);
        }
    }

    vector<vector<int>> getSkyline(vector<vector<int>>& buildings) {
        //获取第一个关键点
        vector<vector<int>> vec;
        priority_queue<pair<int, int>> que;
        if (!buildings.empty()){
            pair<int, int> par = pair<int, int>(buildings[0][0], buildings[0][2]);
            //第一个关键点
            vectorPush(vec, vector<int>({buildings[0][0], buildings[0][2]}));
            //右边界和高度入堆
            que.push(pair<int, int>(buildings[0][1], buildings[0][2]));
        }else{
            return vec;
        }
        for (int i = 1; i < buildings.size(); i++){
            if (que.empty()){
                //当前点设为关键点
                vectorPush(vec, vector<int>({buildings[i][0], buildings[i][2]}));
            }else{
                if (que.top().first < buildings[i][0]){
                    //设置接地点
                    vectorPush(vec, vector<int>({que.top().first, 0}));
                    //当前点设为关键点
                    vectorPush(vec, vector<int>({buildings[i][0], buildings[i][2]}));
                    //清空堆
                    while(!que.empty()) que.pop();
                }else if (que.top().first == buildings[i][0] && que.top().second == buildings[i][2]){
                    //清空堆
                    while(!que.empty()) que.pop();
                }else if (que.top().first > buildings[i][0] && que.top().second == buildings[i][2]){
                    //清空堆
                    while(!que.empty()) que.pop();
                }else{
                    stack<pair<int, int>> sta;
                    stack<pair<int, int>> sta2; 
                    int min = buildings[i][2];
                    while(!que.empty()){
                        pair<int, int> popTop = que.top();
                        que.pop();
                        if (popTop.first > buildings[i][0]){
                            if (popTop.second > min){
                                // que.push(pair<int, int>(buildings[i][0], popTop.second));
                                sta.push(pair<int, int>(popTop.first, min));
                                min = popTop.second;
                            }
                            //存储比较大的堆顶元素
                            sta2.push(popTop);
                        }else{
                            //清空堆
                            while(!que.empty()) que.pop();
                        }
                    }
                    //恢复弹出的堆顶元素
                    while(!sta2.empty()){
                        que.push(sta2.top());
                        sta2.pop();
                    }
                    if (!sta.empty()){
                        while(!sta.empty()){
                            // que.push(sta.top());
                            vectorPush(vec, vector<int>({sta.top().first, sta.top().second}));
                            sta.pop();
                        }
                    }else{
                        //当前点设为关键点  
                        vectorPush(vec, vector<int>({buildings[i][0], buildings[i][2]}));
                    }
                }
            }
            //当前点入堆
            que.push(pair<int, int>(buildings[i][1], buildings[i][2]));
        }
        //最后一个关键点
        if (!vec.empty()){
            if (vec.back()[0] == buildings[buildings.size()-1][1]){
                vec.back()[1] = 0;
            }else{
                vec.push_back({buildings[buildings.size()-1][1], 0});
            }
        }else{
            vec.push_back({buildings[buildings.size()-1][1], 0});
        }
        return vec; 
    }
};

int main()
{
    Solution su;
    su.test.push_back({
        {2, 9, 10}, {3, 7, 15}, {5, 12, 12}, {15, 20, 10}, {19, 24, 8}
    });
    su.test.push_back({
        {0,2,3}, {2,5,3}
    });
    su.test.push_back({
        {1,2,1}, {1,2,2}, {1,2,3}
    });
    for (int i = 0; i < su.test.size(); i++){
        vector<vector<int>>  result = su.getSkyline(su.test[i]);
        printf("the %dth result is %d\r\n", i, result[0][0]);
    }

    return 0;
}